#!/usr/bin/env python2.5
################################################################################
#
#   adjacent_pairs_iterate.py
# 
# 
#       iterate successive pairs in a list or tuple
#
#
#   Copyright (C) 2007 Leo Goodstadt
#
#   This program is free software; you can redistribute it and/or
#   modify it under the terms of the GNU General Public License
#   as published by the Free Software Foundation; version 2
#   of the License
#
#   This program is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU General Public License for more details.
#
#   You should have received a copy of the GNU General Public License
#   along with this program; if not, write to the Free Software
#   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
#################################################################################


    
    
#_________________________________________________________________________________________

#   lookup_gene_index

#_________________________________________________________________________________________
sub lookup_gene_index($\@\%\%)
{
    my ($gene_name, $gene_to_cluster, $gene_to_index, $gene_from_index) = @_;
    if (!exists $gene_to_index->{$gene_name})
    {
        # start with cluster zero (unclustered)
        push(@$gene_to_cluster, 0);

        # remember index of gene as position in array gene_to_cluster
        my $gene_index = @$gene_to_cluster - 1;
        $gene_from_index->{$gene_index} = $gene_name;
        $gene_to_index->{$gene_name} = $gene_index;
        return $gene_index;
    }
    
    return $gene_to_index->{$gene_name};
}


def get_cluster_total(gene_clusters):
    all_genes = set()
    for gene_cluster in gene_clusters:
        all_genes.extend(gene_cluster)
    return all_genes

    
#_________________________________________________________________________________________

#   cluster_from_pairs


#_________________________________________________________________________________________
def cluster_from_pairs (name_pairs):
    """
       input:  name_pairs
       output: cluster of names (array of array of names)
    
    """

    # which cluster a particular name belongs to:
    # : name_to_cluster[name_index] = cluster_index
    name_to_cluster = list()

    # look up name_index from name_name
    name_to_index    = dict()
    name_from_index  = dict()


    # each entry is an array of name_index in that cluster
    name_clusters = list([]);

    for name1, name2 in name_pairs:
        
        # DEBUG
        # print name1, name2

        # get indices of names
        id1 = lookup_name_index(name1, name_to_cluster, 
                                name_to_index, name_from_index);
        id2 = lookup_name_index(name2, name_to_cluster, 
                                name_to_index, name_from_index);

        curr_cluster1 = name_to_cluster[id1];
        curr_cluster2 = name_to_cluster[id2];

        #
        # add new cluster if neither is yet clustered
        #
        if ($curr_cluster1 + $$curr_cluster2 == 0)
        {
            # cluster index for these two names
            $$curr_cluster1 =
            $$curr_cluster2 = scalar @name_clusters;

            # these two names make up a new cluster
            push(@name_clusters, [$id1, $id2]);
            # print STDERR "\tNew cluster $id1=$name_from_index{$id1}, ".
            #           "$id2=$name_from_index{$id2} in cluster = ",
            #           @name_clusters - 1, "\n";
        }


        #
        # link cluster 2 to cluster 1 if both already have clusters
        #
        elsif ($$curr_cluster1 && $$curr_cluster2)
        {
            next if $$curr_cluster1 == $$curr_cluster2;
            my $cluster1_names = $name_clusters[$$curr_cluster1];
            my $cluster2_names = $name_clusters[$$curr_cluster2];

            # print STDERR "\tMerge clusters $$curr_cluster1 <= $$curr_cluster2 \n";
            # print STDERR "\tBefore: cluster 1= ";
            # print STDERR $name_from_index{$_}, "," for (@$cluster1_names);
            # print STDERR "\n";
            # print STDERR "\tBefore: cluster 2= ";
            # print STDERR $name_from_index{$_}, "," for (@$cluster2_names);
            # print STDERR "\n";


            # save old cluster id 
            # (will be obliterated when assign cluster id of 1 to cluster 2)
            my $old_cluster = $$curr_cluster2;

            # merge cluster 2 into cluster 1
            push(@$cluster1_names, @$cluster2_names);

            # assign curr_cluster1 to all of curr_cluster2 names;
            $name_to_cluster[$_] = $$curr_cluster1 for (@$cluster2_names);

            # cluster 2 holds nothing now
            $name_clusters[$old_cluster] = [];

        }

        #
        # add name 2 to cluster 1 if name 2 is unclustered
        #
        elsif ($$curr_cluster1)
        {
            $$curr_cluster2 = $$curr_cluster1;
            my $cluster1_names = $name_clusters[$$curr_cluster1];
            push(@$cluster1_names, $id2);

            # print STDERR "\tAdd to cluster $$curr_cluster1 <= $name_from_index{$id2} \n";
            # print STDERR "\tAfter: cluster $$curr_cluster1= ";
            # print STDERR $name_from_index{$_}, "," for (@$cluster1_names);
            # print STDERR "\n";
        }

        #
        # add name 1 to cluster 2 if name 1 is unclustered
        #
        else
        {
            $$curr_cluster1 = $$curr_cluster2;
            my $cluster2_names = $name_clusters[$$curr_cluster2];
            push(@$cluster2_names, $id1);

            # print STDERR "\tAdd to cluster $$curr_cluster2 <= $name_from_index{$id1} \n";
            # print STDERR "\tAfter: cluster $$curr_cluster2= ";
            # print STDERR $name_from_index{$_}, "," for (@$cluster2_names);
            # print STDERR "\n";
        }

    }
    my @final_name_clusters;
    #
    # copy non-empty clusters to output set
    #
    for my $name_cluster(@name_clusters)
    {
        next unless @$name_cluster;
        push(@final_name_clusters,
             [map {$name_from_index{$_};} @$name_cluster]);
    }

    return @final_name_clusters;
